/*
 * @lc app=leetcode.cn id=20 lang=cpp
 *
 * [20] 有效的括号
 */

// @lc code=start
class Solution {
public:
    bool isValid(string s) {
        std::unordered_map<char, char> brackets {
            {'(', ')'},
            {'[', ']'},
            {'{', '}'}
        };

        std::stack<char> st;
        for (int i = 0; i < s.size(); i++) {
            //左括号, 入栈
            if (brackets.find(s[i]) != brackets.end()) {
                st.push(s[i]);
                continue;
            }

            //右括号, 栈空 || 和栈顶不匹配
            if (st.size() == 0 || s[i] != brackets[st.top()])
                return false;
            
            //匹配则出栈, 检索下一对
            st.pop();
        }

        if (st.size() > 0)
            return false;

        return true;
    }
};
// @lc code=end

